#define _CRT_SECURE_NO_WARNINGS 1
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
const int N = 100001;
bool isEvenOddTree(struct TreeNode* root) {
    struct TreeNode* q[N];
    int hh = 0;
    int tt = 0;
    q[tt++] = root;
    int d = 0;
    while (hh < tt) {
        int sz = tt - hh;
        int pre;
        if (d % 2)pre = 1e9;
        else pre = -1e9;
        for (int i = 0; i < sz; i++) {
            struct TreeNode* it = q[hh++];
            int v = it->val;
            if ((d % 2 && v % 2) || (d % 2 && v >= pre))return false;
            if ((!d % 2) && !(v % 2)) || (!(d % 2) && v <= pre))return false;
            pre = v;

            if (it->left) q[tt++] = it->left;
            if (it->right)q[tt++] = it->right;
        }
        d++;
    }
    return true;
}